An erasure code is a forward error correction (FEC) code that transforms a message of x symbols into a longer message, or code word, with y code word symbols such that the original message can be recovered from a subset of the y code word symbols. An erasure code is referred to an optimal erasure code if x of the n code word symbols are sufficient to recover the original message. Optimal erasure codes are maximum distance separable codes (MDS codes).
An optimal erasure code may be based on a parity check-sum and/or polynomial interpolation with points computed over a finite field. Polynomial interpolation may be implemented with Reed-Solomon FEC encoding, with code words constructed over a finite field using a Vandermonde matrix.
RAID is a data storage virtualization technology that combines multiple disk drive components into a logic unit to improve performance (e.g., reduce access times) and/or to provide data recoverability, also referred to herein as data reliability and/or data resiliency. The term “RAID” was introduced by David Patterson, Garth A. Gibson, and Randy Katz at the University of California, Berkeley in 1987, as an acronym for a redundant array of inexpensive disks. RAID is also used as an acronym for a redundant array of independent disks.
RAID standards have been published as a Common RAID Disk Drive Format (DDF) by the Storage Networking Industry Association (SNIA), of San Francisco, Calif. RAID standards currently include RAID 0 through RAID 6. Non-standard RAID configurations are discussed in literature.
RAID 6 is “[a]ny form of RAID that can continue to execute read and write requests to all of a RAID array's virtual disks in the presence of any two concurrent disk failures. Several methods, including dual check data computations (parity and Reed-Solomon), orthogonal dual parity check data and diagonal parity, have been used to implement RAID Level 6.” (The 2013 SNIA Dictionary, v. 2013.2.ENG, SNIA, San Francisco, Calif.). RAID 6 thus provides data resiliency for up to 2 disk failures.
For RAID 6, two syndromes, P and Q, are computed to permit recovery from a loss of any two drives. Syndrome P may be computed as an XOR of the data across the stripes with relatively little processor overhead. Syndrome Q is more complicated and may be computed with field theory.
In the drawings, the leftmost digit(s) of a reference number identifies the drawing in which the reference number first appears.